/*
 * Antonio Canabrava Fraideinberze 7152292
 * Lucas Avelino Sodre Santos      7239086
 * Pedro Rael Garcia               7153021
 */

/*
 * Algorithm of Sieve of Eratosthenes - Parallel version
 *
 * In this algorithm was used Data Decomposition, what is
 * every process calculates some piece of the whole sieve.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <mpi.h>

/*
 * This defines the LAST_PRIME as 10000, because the sum of the
 * biggest palindrome characters isn't bigger that it.
 */
#define LAST_PRIME 10000

/* definition of the root process */
#define ROOT 0

int
main(int argc, char *argv[])
{
    int i;
    int id, p;
    int low_value, high_value, size;
    int prime, index, first;
    int tag = 0;
    MPI_Status status;
    MPI_Request reqS, reqR;
    /*
     * Vectors offsets and counts of process
     * it will be used in MPI_Gatherv
     */
    int *offset;
    int *process;
    /*
     * Data sets that will be used by each process to calculate
     * your own part of the sieve.
     */
    char *marked;
    char *all;
    /* File that will store the prime numbers */
    FILE *of;
    /* Initialization of the MPI functions */
    MPI_Init(&argc, &argv);
    /* Important info for the program */
    MPI_Comm_rank(MPI_COMM_WORLD, &id);
    MPI_Comm_size(MPI_COMM_WORLD, &p);
    /* Calculates the lower and the higher value, and the size of the block */
    low_value = 2 + (id * LAST_PRIME / p);
    high_value = 1 + ((id + 1) * LAST_PRIME / p);
    size = high_value - low_value;
    /* Allocates memory to each part of the sieve */
    marked = (char *) malloc(size + 1);

    for(i = 0; i <= size; i++)
        marked[i] = 'y';

    if(id != ROOT)
    {
        MPI_Isend(&size, 1, MPI_INT, ROOT, tag, MPI_COMM_WORLD, &reqS);
    }

    else if(id == ROOT)
    {
        process = (int *) malloc(p + 1);
        process[0] = size;

        for(i = 1; i < p; i++)
        {
            MPI_Irecv(&process[i], 1, MPI_INT, i, tag, MPI_COMM_WORLD, &reqR);
            MPI_Wait(&reqR, &status);
        }

        index = 0;
    }

    /* First prime number */
    prime = 2;

    /* Calculates prime numbers */
    do
    {
        if(low_value % prime == 0)
            first = ((low_value / prime) * prime) - low_value;

        else
            first = (((low_value / prime) * prime) + prime) - low_value;

        /* Set all multiples of prime as not prime */
        if(id == ROOT)
            for(i = first + prime; i <= size; i += prime)
                marked[i] = 'n';

        else
            for(i = first; i <= size; i += prime)
                marked[i] = 'n';

        /* Searchs for the next prime in the root partition */
        if(id == ROOT)
        {
            do
            {
                index++;
            }
            while(marked[index] == 'n');

            prime = index + 2;
        }

        /* Broadcasts the next prime to every process from the root */
        MPI_Bcast(&prime, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
    }
    while(prime * prime <= LAST_PRIME);

    /* Here starts the alternative to MPI_Gatherv */
    if(id != ROOT)
        MPI_Send(marked, size, MPI_CHAR, ROOT, tag, MPI_COMM_WORLD);

    /* The process tells the root the size of its calculated sieve */
    /* Calculates the offset of each process' sieve */
    else if(id == ROOT)
    {
        char tmp[LAST_PRIME];
        offset = (int *) malloc(p);

        for(i = 0; i < p; i++)
            offset[i] = (i > 0) ? (offset[i - 1] + process[i - 1]) : 0;

        /* If I'm the root, gether all the sieves' part in one big set */
        all = (char *) malloc(LAST_PRIME + 2);
        /* Here continues the alternative solution */
        strncpy(all, marked, size);

        for(i = 1; i < p; i++)
        {
            MPI_Recv(tmp, process[i], MPI_CHAR,
                     i, tag, MPI_COMM_WORLD, &status);
            strncpy(all + offset[i - 1] + process[i - 1] + i, tmp, process[i]);
        }

        /* Here the alternative solution ends*/
        /* If I'm the root, print all the primes */
        of = fopen("res", "w");

        for(i = 0; i <= LAST_PRIME; i++)
            if(all[i] == 'y')
                fprintf(of, "%d ", i + 2);

        /* Free memory allocated by the root process */
        fclose(of);
        free(process);
        free(offset);
        free(all);
    }

    /* Free all allocated memory */
    free(marked);
    /* Finalize the MPI funcions */
    MPI_Finalize();
    return 0;
}
